package com.asa.ui.G;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 迷宫的随机自动生成器
 * 
 * @author asa
 *
 */
public class MapCreate {

	public static void main(String[] args) {

		map2d();

	}

	public static String[][] map2d() {
		int h = 20;
		int w = 30;

		String[][] asa = new String[h][w];
		for (int i = 0; i < asa.length; i++) {
			for (int j = 0; j < asa[i].length; j++) {

				asa[i][j] = "#";

			}
		}

		// 初始化入口和出口
		int[] start = { 1, 0 };
		int[] end = { h - 2, w - 1 };
		updateOne(start, " ", asa);
		updateOne(end, " ", asa);

		int curi = start[0];
		int curj = start[1];
		Random random = new Random();
		// 随机生成一条联通解
		while (true) {

			// 随机生成下一步
			int nextsteepi = nextsteep();
			int nextsteepj = nextsteep();

			// 试探下一步是否合法

			if (nextsteep() > 0) {
				if (curj + nextsteepj <= 0 || curj + nextsteepj >= w - 1 || curi <= 0 || curi >= h) {
					// 判断已经生成完毕了，就跳出生成循环逻辑
					if (curi == end[0] && curj + nextsteepi == end[1]) {
						break;
					}
					continue;
				}

				if (notConnect(curi, curj, asa, curi, curj + nextsteepj, end)>0) {
//					updateOne(curi,curj, "#", asa);
					
					
					int[] notConnectIndexs = notConnectIndexs(curi, curj, asa, curi, curj + nextsteepj, end);
					
					curi = notConnectIndexs[0];
					curj = notConnectIndexs[1];
						
					

					continue;
				}

				curj = curj + nextsteepj;
				updateOne(curi, curj, " ", asa);

			} else {
				if (curi + nextsteepi <= 0 || curi + nextsteepi >= h - 1 || curj <= 0 || curj >= w) {
					// 判断已经生成完毕了，就跳出生成循环逻辑
					if (curi + nextsteepi == end[0] && curj == end[1]) {
						break;
					}
					continue;
				}
				// 存在路径环路打结问题，这个处理方式有点粗暴
				if (notConnect(curi, curj, asa, curi + nextsteepi, curj, end)>0) {
					
					
//					updateOne(curi,curj, "#", asa);
					int[] notConnectIndexs = notConnectIndexs(curi, curj, asa, curi + nextsteepi, curj, end);
					curi = notConnectIndexs[0];
					curj = notConnectIndexs[1];
					continue;
				}
				curi = curi + nextsteepi;
				updateOne(curi, curj, " ", asa);

			}

//			if(1==1) {
//				break;
//			}
//			printMap(asa);
//			System.out.println("---------------------------------------------");

		}

		// 上面只是生成了一个可联通的路径，但这条路径上还是有干扰项目，就是说，不那么规整，有毛刺路径，可以考虑先求个迷宫路径解，清一下非这个路径上的毛刺，优化方向

		// 生成迷宫的干扰路径
		// 生成多少个呢？
		int deadLu = 500;// 尝试生成10条死路

		for (int i = 0; i < deadLu; i++) {

			int[] startpoint = startpoint(asa);
			curi = startpoint[0];
			curj = startpoint[1];

			while (true) {

				// 随机生成下一步
				int nextsteepi = nextsteep();
				int nextsteepj = nextsteep();

				boolean first = true;

				// 试探下一步是否合法
				if (nextsteep() > 0) {
					if (curj + nextsteepj <= 0 || curj + nextsteepj >= w - 1 || curi <= 0 || curi >= h) {
						// 判断已经生成完毕了，就跳出生成循环逻辑
						if (curi == end[0] && curj + nextsteepi == end[1]) {
							break;
						}
						continue;
					}

					if (notConnect(curi, curj, asa, curi, curj + nextsteepj, end)>0) {
						
//						updateOne(curi,curj, "#", asa);
						int[] notConnectIndexs = notConnectIndexs(curi, curj, asa, curi, curj + nextsteepj, end);
						curi = notConnectIndexs[0];
						curj = notConnectIndexs[1];

						continue;
					}
					if (asa[curi][curj + nextsteepj] == " "
							) {
						if(!first) {
							updateOne(curi, curj, "#", asa);
							updateOne(curi , curj + nextsteepj, "#", asa);

						}
						if (notConnect(curi, curj, asa, curi , curj+ nextsteepj, end)>2) {
							updateOne(curi, curj, "#", asa);

						}
						
						break;
					}
					curj = curj + nextsteepj;
					
					updateOne(curi, curj, " ", asa);

				} else {
					if (curi + nextsteepi <= 0 || curi + nextsteepi >= h - 1 || curj <= 0 || curj >= w) {
						// 判断已经生成完毕了，就跳出生成循环逻辑
						if (curi + nextsteepi == end[0] && curj == end[1]) {
							break;
						}
						continue;
					}
					// 存在路径环路打结问题，这个处理方式有点粗暴
					if (notConnect(curi, curj, asa, curi + nextsteepi, curj, end)>0) {
						
//						updateOne(curi,curj, "#", asa);
						int[] notConnectIndexs = notConnectIndexs(curi, curj, asa, curi + nextsteepi, curj, end);
						curi = notConnectIndexs[0];
						curj = notConnectIndexs[1];
						continue;
					}
					if (asa[curi + nextsteepi][curj] == " "
							) {
						if(!first) {
							updateOne(curi, curj, "#", asa);

						}
						if (notConnect(curi, curj, asa, curi + nextsteepi, curj, end)>2) {
							updateOne(curi, curj, "#", asa);

						}

						
						
						break;
					}
					
					curi = curi + nextsteepi;
					
					updateOne(curi, curj, " ", asa);

				}
				first = false;

			}

		}

		for (int i = 1; i < asa.length-1; i++) {
			for (int j = 1; j < asa[i].length-1; j++) {
				if (asa[i][j] == " ") {
					int notConnect = notConnect(i, j, asa, i , j, end);
					if (notConnect>0) {
						updateOne(i, j, "#", asa);

					}
				}

			}
		}
		
		
		
		printMap(asa);
		return asa;
	}

	/**
	 * 在现有的路径上找干扰路径的起始节点
	 * 
	 * @param asa
	 * @return
	 */
	private static int[] startpoint(String[][] asa) {
		// TODO Auto-generated method stub
		List<int[]> slu = new ArrayList<>();

		for (int i = 1; i < asa.length-1; i++) {
			for (int j = 1; j < asa[i].length-1; j++) {
				if (asa[i][j] == " ") {
					slu.add(new int[] { i, j });
				}

			}
		}

		Random random = new Random();
		int nextInt = random.nextInt(slu.size());

		return slu.get(nextInt);
	}

	/**
	 * 尽量一条路到底
	 * 
	 * @param asa
	 */
	private static int notConnect(int prei, int prej, String[][] asa, int i, int j, int[] end) {
		int countLu = 0;
//		if (i==0) {
//			countLu++;
//		}else 
			if (asa[i - 1][j] == " ") {
			if (i - 1 != prei && j != prej && i != end[0] && j + 1 != end[1])
				countLu++;
		}
//		if (j==0) {
//			countLu++;
//
//		}else 
			if (asa[i][j - 1] == " ") {
			if (i != prei && j - 1 != prej && i != end[0] && j + 1 != end[1])
				countLu++;
		}
			
//		if (i>=asa.length-2) {
//			countLu++;
//
//		}else 
		if (asa[i + 1][j] == " ") {
			if (i + 1 != prei && j != prej && i != end[0] && j + 1 != end[1])
				countLu++;
		}
//		if (j>=asa[0].length-2) {
//			countLu++;
//
//		}else 
			if (asa[i][j + 1] == " ") {
			if (i != prei && j + 1 != prej && i != end[0] && j + 1 != end[1])
				countLu++;
		}
	
		
		
		

		
		
		return countLu;
	}

	private static int[] notConnectIndexs(int prei, int prej, String[][] asa, int i, int j, int[] end) {
		int[] result = new int[2];

		if (asa[i - 1][j] == " ") {
			if (i - 1 != prei && j != prej) {
				result[0] = i - 1;
				result[1] = j;
			}

		}
		if (asa[i][j - 1] == " ") {
			if (i != prei && j - 1 != prej) {
				result[0] = i;
				result[1] = j - 1;
			}
		}
		if (asa[i + 1][j] == " ") {
			if (i + 1 != prei && j != prej) {
				result[0] = i + 1;
				result[1] = j;
			}
		}
		if (asa[i][j + 1] == " ") {
			if (i != prei && j + 1 != prej) {
				result[0] = i;
				result[1] = j + 1;
			}
		}
		return result;
	}

	/**
	 * 打印地图
	 * 
	 * @param asa
	 */
	private static void printMap(String[][] asa) {
		for (int i = 0; i < asa.length; i++) {
			for (int j = 0; j < asa[i].length; j++) {

				System.out.print(asa[i][j]);
			}
			System.out.println();
		}
	}

	/**
	 * 下一步走向
	 * 
	 * @return
	 */
	public static int nextsteep() {
		Random random = new Random();

		int nextInt = random.nextInt(2);

		if (nextInt == 0) {
			nextInt = -1;
		}

		return nextInt;
	}

	public static void updateOne(int[] indexs, String update, String[][] asa) {
		updateOne(indexs[0], indexs[1], update, asa);
	}

	public static void updateOne(int indexi, int indexj, String update, String[][] asa) {
		asa[indexi][indexj] = update;
	}

}
